import collections
import heapq
class Solution(object):
    def countPaths(self, n, roads):
        d = collections.defaultdict(lambda:collections.defaultdict(int))
        for u, v, t in roads:
            d[u][v] = t
            d[v][u] = t
        dist = [-1] * n
        dist[0] = 0
        times = [0] * n
        times[0] = 1
        st = []
        for v in d[0]:
            st.append([d[0][v], v, 0])
        heapq.heapify(st)
        while st:
            while st and dist[st[0][1]] >= 0:
                q, u, last = heapq.heappop(st)
                if q == dist[u]:
                    times[u] += times[last]
            if st:
                q, u, last = heapq.heappop(st)
                dist[u] = q
                times[u] += times[last]
                for v in d[u]:
                    heapq.heappush(st, [d[u][v] + dist[u], v, u])
        return times[-1] % (10 ** 9 + 7)

data = Solution()
n = 7
roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
print(data.countPaths(n, roads))


